// https://www.lintcode.com/problem/find-the-duplicate-number/description

class Solution {
public:
    /**
     * @param nums: an array containing n + 1 integers which is between 1 and n
     * @return: the duplicate one
     */
    // 要求空间O(1)
    // 法一：双重for循环
    
    // 法二：排序后遍历 O(n)  或者找到第一个A[i]<=i的数 O(nlogn)
    // int findDuplicate(vector<int> &nums) {
    //     // write your code here
    //     sort(nums.begin(), nums.end());
    //     for (int i = 1; i < nums.size(); ++i) {
    //         if (nums[i] == nums[i - 1]) {
    //             return nums[i];
    //         }
    //     }
    // }
    
    // 法三：快慢指针 O(n)
    // 如果把数据看做一个 LinkedList，第 i 个位置上的值代表第 i 个点的下一个点是什么的话，我们就能画出一个从 0 出发的，一共有 n + 1 个点的 Linked List。
    // 可以证明的一件事情是，这个 Linked List 一定存在环。因为无环的 Linked List 里 非空next 的数目和节点的数目关系是差一个（节点多，非空next少）
    // 那么，我们证明了这是一个带环链表。而我们要找的重复的数，也就是两个点都指向了同一个点作为 next 的那个点。也就是环的入口。
    // int findDuplicate(vector<int> &nums) {
    //     if (nums.size() <= 1)
    //         return -1;

    //     int slow = nums[0];
    //     int fast = nums[nums[0]];
    //     while (slow != fast) {
    //         slow = nums[slow];
    //         fast = nums[nums[fast]];
    //     }
    //     slow = 0;
    //     while (slow != fast) {
    //         slow = nums[slow];
    //         fast = nums[fast];
    //     }
    //     return slow;
    // }
    
    // 法三：二分+遍历 O(nlogn) 
    int check(vector<int> nums, int n) {
        int cnt = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] <= n) {
                cnt++;
            }
        }
        return cnt;
    }
    int findDuplicate(vector<int> &nums) {
        int low = 0;
        int high = nums.size() - 1;
        while (low + 1 < high) {
            int mid = (high - low) / 2 + low;
            if (check(nums, mid) <= mid) {
                low = mid;
            } else {
                high = mid;
            }
        }
        if (check(nums, low) <= low) {
            return high;
        } else {
            return low;
        }
    }
};